package com.lxl.merge;

import java.util.Arrays;

/**
 * @Classname MinSum
 * @Description 归并排序应用 数组小和
 * @Date 2021/8/16 9:41
 * @Created by LXLDEMO
 */
public class MinSum {

    public static void main(String[] args) {

        // 测试数据
        int[] arr = {2,4,3,1,6,5};
        minSum(arr);

    }


    /**
     * 求数组小和
     * @param arr
     */
    public static void minSum(int[] arr){
        if (arr == null || arr.length<2){
            System.out.println("所求小和为 0");
            return;
        }

        int[] temp = new int[arr.length];
        int minsum = mergeSort4MinSum(arr,temp,0,arr.length-1);

        System.out.println("所求小和值为 "+minsum);
    }


    /**
     * 求数组小和
     * @param arr
     * @param temp
     * @param start
     * @param end
     * @return
     */
    public static int mergeSort4MinSum(int[] arr,int[] temp,int start,int end){
        if (start >= end){
            return 0;
        }
        int mid = (start + end) / 2;

        // 排序第一个数组 计算第一个数组小和
        int leftMinSum = mergeSort4MinSum(arr,temp,start,mid);
        // 排序第二个数组 计算第二个数组小和
        int rughtMinSum = mergeSort4MinSum(arr,temp,mid+1,end);
        // 合并两个有序数组 计算总的数组小和
        int allMinSum = merge4MinSum(arr,temp,start,mid,end);

        return leftMinSum + rughtMinSum +allMinSum;
    }

    /**
     * 求数组小和
     * @param arr   存放两个有序列表的数组
     * @param temp  临时数组
     * @param start 左侧有序列表开始的下标
     * @param mid   左侧结束位置下标  右侧开始位置下标：mid+1
     * @param end   右侧有序列表结束下标
     * @return 本组小和
     */
    public static int merge4MinSum(int[] arr,int[] temp,int start,int mid,int end){
        System.out.println("前一组开始下标 "+start);
        System.out.println("前一组结束下标 "+mid);
        System.out.println("后一组开始下标 "+(mid+1));
        System.out.println("后一组结束下标 "+end);
        int i = start; // i 用来记录 第一个数组的遍历位置
        int j = mid + 1; // 用来记录第二个数组的遍历位置
        int k = start; // 用来表示临时数组的下标
        int minSumResult = 0;
        // i=mid+1:第一个数组先遍历完成
        // j=end+1:第二个数组先遍历完成
        while (i != mid +1 && j != end +1){
            if (arr[i]>arr[j]){
                temp[k++] = arr[j++];
            }else {
                minSumResult += arr[i]<arr[j]?(end-j+1) * arr[i]:0; // 计算小和语句
                temp[k++] = arr[i++];
            }
        }
        // 第一个数组没有遍历完毕
        while (i != mid + 1){
            temp[k++] = arr[i++];
        }

        // 第二个元素没有遍历完毕
        while (j != end + 1){
            temp[k++] = arr[j++];
        }

        for (int n = start;n<=end;n++){
            arr[n] = temp[n];
        }
        System.out.println("本次合并结果："+ Arrays.toString(arr));
        return minSumResult;
    }
}
